﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BinaryTreeCode
{
   
    class SymmetryTree
    {
        //=================================力扣101 对称二叉树
        //给定一个二叉树，检查它是否是镜像对称
        //思路：其实就是比较根节点的两个子树的里侧和外侧元素是否相等，所以我们需要遍历两棵树
        //递归法
        public bool IsSymmetric(TreeNode root)
        {
            if (root == null)
                return true;
            return Compare(root.left, root.right);
        }
        private bool Compare(TreeNode left, TreeNode right)
        {
            //排除空节点
            if (left == null && right != null)
                return false;
            else if (left != null && right == null)
                return false;
            else if (left == null && right == null)
                return true;
            //排除数值不同的情况
            else if (left.val != right.val)
                return false;

            //以下是左右节点均不为空，且数值相同的情况
            bool outside = Compare(left.left, right.right);//左子树：左、右子树：右 （即外侧）
            bool inside = Compare(left.right, right.left);//左子树：右、右子树：左 （即内侧）
            bool isSame = outside && inside;//逻辑处理
            return isSame;
        }

        //迭代法(队列）
        public bool IsSymmetric_2(TreeNode root)
        {
            if (root == null)
                return true;
            Queue<TreeNode> que = new Queue<TreeNode>();
            que.Enqueue(root.left);//将左子树头结点加入队列
            que.Enqueue(root.right);//将右子树头结点加入队列
            while(que.Count > 0)
            {//判断两个数是否互相翻转
                TreeNode leftnode = que.Dequeue();
                TreeNode rightnode = que.Dequeue();
                if (leftnode == null && rightnode == null)
                    continue;//左节点和右节点均为空，说明是对称的

                if (leftnode == null || rightnode == null || (leftnode.val != rightnode.val))
                    return false;//节点有一个不为空，或者都不为空但数值不同返回false

                que.Enqueue(leftnode.left);
                que.Enqueue(rightnode.right);
                que.Enqueue(leftnode.right);
                que.Enqueue(rightnode.left);
            }
            return true;
        }

        //迭代法(栈）
        public bool IsSymmetric_3(TreeNode root)
        {
            //跟使用队列一毛一样，反正每次都成对push
            return false;
        }

        //=========================================力扣100 相同的树
        //给你两个二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同
        public bool IsSameTree(TreeNode p, TreeNode q)
        {//迭代法
            if (p == null && q == null)
                return true;
            Stack<TreeNode> st = new Stack<TreeNode>();
            st.Push(p);
            st.Push(q);
            while(st.Count > 0)
            {
                TreeNode leftNode = st.Pop();
                TreeNode rightNode = st.Pop();
                if (leftNode == null && rightNode == null)
                    continue;

                if (leftNode == null || rightNode == null || leftNode.val != rightNode.val)
                    return false;

                st.Push(leftNode.left);
                st.Push(rightNode.left);
                st.Push(leftNode.right);
                st.Push(rightNode.right);
            }
            return true;
        }

        public bool IsSameTree_2(TreeNode p, TreeNode q)
        {//递归法
            if (p == null && q != null)
                return false;
            else if (p != null && q == null)
                return false;
            else if (p == null && q == null)
                return true;
            else if (p.val != q.val)
                return false;

            return IsSameTree_2(p.left, q.left) && IsSameTree_2(p.right, q.right);
        }

        //===================================力扣572 另一颗树的子树
        //给您两颗二叉树root和subRoot。检验Root中是否包含和subRoot具有相同结构的节点值和子树。如果存在返回true，否则返回flase
        //深度优先搜索暴力匹配
        public bool IsSubtree(TreeNode root, TreeNode subRoot)
        {
            if (root == null)
                return false;
            return CheckIsSame(root, subRoot) || IsSubtree(root.left, subRoot) || IsSubtree(root.right, subRoot);
        }
        private bool CheckIsSame(TreeNode p,TreeNode q)
        {
            if (p == null && q != null)
                return false;
            else if (p != null && q == null)
                return false;
            else if (p == null && q == null)
                return true;
            else if (p.val != q.val)
                return false;

            return CheckIsSame(p.left, q.left) && CheckIsSame(p.right, q.right);
        }
       
        //其他方法二 有空看

    }
}
